The invention generally relates to methods and apparatus for coding and decoding signals and, more specifically, to methods and apparatus for convolutional decoding.
The instant invention is directed to improving the communication of digital radio information. Digital information may be conceptualized as a message composed of binary bits of information, where each bit can either be a ONE or a ZERO. Any given message is then just a string comprising a number of ONEs interspersed with a number of ZEROs. It will be appreciated that any string of L bits can represent one of 2.sup.L unique messages.
One of the fundamental difficulties encountered by radio communications systems is the presence of noise in the communications channels. Noise can cause serious problems in a digital communications environment. Noise encountered during digital radio communications can result in bit errors in the transmitted information. The bit errors, in turn, may render the information useless, or worse (e.g., the receiving system determines the information to be correct when it is actually in error). In order to combat noisy channels, and thereby reduce bit errors, digital radio communications systems typically employ both error detecting and error correcting circuits.
A simple example of error detection coding is as follows: for any one digital message add an identical copy of that message to the original message, transmit both the original and copy, and perform a bit-by-bit comparison of the received message with the received copy. For each bit position, any disagreement between the message and the copy is evidence of a transmission error. The total number of disagreements for a message is a quantitative measure of the reliability of the data transmission. However, it will be appreciated that the total number of disagreements is an inexact measure of reliability because simultaneous errors at the same bit position in both the message and the copy are not recognized as disagreements.
A common technique for error detection is the use of a Cyclic Redundancy Check (CRC). A CRC involves creating a set of parity bits at the transmitter from the information bits desired to be transmitted. The parity bits constitute a "check word" specific to a given message. The check word may be appended to the message so that both are processed through the same transmitter, both are transmitted through the communications channel together, and both are processed through the same decoder at the receiver. A CRC calculator in the receiver may then generate parity bits corresponding to the decoded message bits that were received. The receiver-calculated check word may then be compared with the decoded check word that was received with the message. Any non-compliance indicates an error detected in the transmission.
By way of contrast, a simple example of error correction coding is transmitting several identical copies of a given message and performing a bit-by-bit comparison of all messages received at the receiver. Whether a bit of the message output from the receiver should be a ONE or a ZERO may be decided on the basis of comparing all the bits received for each position of the message and allowing the majority of agreeing bit values received for that bit position to determine the output. Transmission errors generally may be assumed to be randomly distributed among the message copies and will thus be less likely to occur at the same bit position in a majority of the copies, allowing the receiver to determine the correct bit value for each position.
A well known technique for error detection and correction is the use of block codes. Block codes divide the sequence of source digits into sequential blocks of L digits. Each L digit block is mapped into a unique n digit block of output digits, known as a codeword, where n&gt;L. Coded and uncoded blocks are compared on the basis that both systems use the same total time duration for a transmitted message. A block code can be linear or nonlinear. A linear block code can be either cyclical or non-cyclical. A cyclical block code can have correction and detection capability. The ratio of total number of information bits to the total number of bits in the code word (L/n) is referred to as the code rate, and is a measure of code efficiency. The difference (1-L/n) is called the redundancy. The encoder is said to produce an (n, L) code. Block codes are memoryless codes because each output code depends on only one source L-bit block and not any preceding blocks or digits. The lower the code rate, the more efficient the code is. However, block coding has a limited error detection capability. If the number of error bits exceeds the error detection capability of the block code, the decoding process may output a valid code word which is not the transmitted code word. In this case, a missed detection occurs.
Another well known technique for error correction include the use of convolutional codes. Convolutional codes, unlike block codes, depend on the immediately preceding stream of received message bits. In convolutional coding, information bits are encoded and decoded in such a way as to determine bits which are destroyed in transmission. A convolutional code is typically described by the rate of the code, its constraint length, and various parity equations.
For example, a convolutional code having a rate of L/n, wherein n coded bits are produced for each set of L information bits, a constraint length of k, can be implemented in a shift register of length k minus one bit. At each interval, L information bits are shifted into the register and n bits are produced to be transmitted. The coded bits are combinations (linear algebraic functions) of the contents of the shift register and the most recent input bit. These combinations vary, depending on the convolutional code used. Unlike block codes, the coded bits from a convolutional code can not be grouped as information bits and parity bits.
The transmitted bits are decoded at the receiver. The receiver knows the code parameters for the corresponding code used by the transmitter/encoder in order to decode the information. Convolutional decoding corrects errors by determining the information where a bit error has occurred, based upon the past received bits, since the encoded bits are derived from several adjacent information bits.
The error-correcting code attempts to remove any errors that might have been introduced by the channel. Of course, not all errors are correctable. Therefore, error detecting codes are used to determine when error correction can be made and appropriate action taken to correct the bits detected in error. Thus, convolutional error correcting codes can be used in conjunction with error detection codes, such as the CRC, to provide a more robust communications system allowing for both the detection and correction of bit transmission errors.
Convolutional coding is one of the best coding schemes for digital communications where energy efficiency dominates in importance. Among the various decoding methods for convolutional codes, Viterbi's maximum likelihood algorithm is one of the best techniques. One form of Sequential Maximum Likelihood sequence estimation (SMLSE), the Viterbi algorithm permits equipment simplification while obtaining the full performance benefits of maximum likelihood decoding. The decoder structure is relatively simple for short constraint length codes, making decoding feasible at high rates of up to 100 Mbits per second. A complete description of Viterbi's algorithm can be found in "The Viterbi Algorithm" by G. David Fornay, Jr. Proceedings of the IEEE, Volume 61, No. 3, March 1973.
The maximum-likelihood receiver implies selecting a code word closest to the actual received message word. Because there are 2.sup.L code words, the maximum likelihood decision involves storage of 2.sup.L words and their comparison with the received word. However, for a large L, the calculations needed would be extremely difficult, resulting in overly complex decoders, making such calculations impractical.
A major simplification was made through Viterbi or SMLSE. Turning to FIGS. 1A and B, the state and trellis diagram for a Rate=1/2 and k=3 convolutional coder is shown. In FIG. 1A, note for an encoder having four states that each of the four states (A, B, C, and D) has only two predecessors; that is, each state can be reached through two possible states only, and only the path that agrees most with a received sequence (the minimum distance path) need be retained for each state. FIG. 1B depicts a trellis diagram showing the possible relations between states. Given a received sequence bit, a path in the trellis diagram is determined so that the output sequence from the decoder is the one that most agrees with the received sequence.
For example, suppose the first six digits received are 010001. Consider two paths of three branches for six digits leading to each of the states A, B, C, and D in FIG. 1A. Out of the two paths reaching each state, only the one that agrees most with the received sequence 010001 is retained. This is often referred to as the minimum distance path. The retained path is called the survivor. There are two paths 000000 and 111011 that arrive at the third level state A. These paths are at distances of two and three, respectively, from the received sequence 010001. Hence, the survivor at the third level state is 000000. The procedure is repeated for states B, C, and D. For example, the two paths reaching to the third level state C, the state after three branches, are 001110 and 110101, at distances of five and two, respectively, from the received sequence of 010001. Hence, the survivor at the third level state C is 110101. Similarly, the survivors are determined at the third level states B and D. With four paths eliminated, the four survivor paths are the only contenders. The reason for eliminating the other four paths is as follows: the two paths merging at the third level state A, for example, imply that the previous two data digits are identical. Hence, regardless of what the future data digits are, both paths must merge at this state A and follow a common path in the future. Clearly, the survivor path is the minimum distance path between the two, regardless of future data digits. Then all that needs to be remembered are the four survivor paths and their distances from the received sequence.
Once the survivors at all of the third level states have been determined, the next two received digits are examined. Suppose these are 11 (i.e., the received sequence is 01000111). The two survivors that merge into the fourth level state A are now composed. These are the survivors at states A and C of the third level, with paths 00000000 and 11010111, respectively, at distances of four and two, from the received sequence 01000111. Hence, the path 11010111 is the survivor at the fourth level state A. This procedure is repeated for states B, C, and D, and continues in this manner until the end. Note that only two paths merge at each state and there are only four contending paths (the four survivors at states A, B, C, and D) until the end. Finally, it can be determined how to terminate the trellis and ultimately decide on one final path rather than four. This can be done by forcing the last two digits at the encoder to be, for example, 00. This forces the final state of the code to be A (note that the last two dated digits 00 corresponds to state A). Consequently, the ultimate survivor is the survivor state A after insertion into the coder of two dummy 00s, called tail bits, and transmission of the corresponding four code digits. In terms of the trellis diagram, this means that the number of ending states is reduced from four to two (A and C) by insertion of the first zero into an ending single state A by insertion of the second zero.
By specifying the starting bit and ending bits known as tail bits, the decoder can decode when a complete code word has been received. However, this results in an increased overhead because the ending bits need to be coded in addition to the actual message information bits. In order to reduce this overhead, a technique known as tail-biting is used. According to this technique, the same starting and ending state is used (e.g., forcing the starting and ending state to be 00 in the example above). However, the reduction in overhead comes at the price of not knowing the beginning state or ending state. This tradeoff increases the decoder complexity by at least a factor of two. It should be noted that, while tail-biting provides good performance at low bit error rates (BERs), it provides a degraded performance at higher BERs.
A third method for determining an ending state is to use the accumulated error metric associated with each state. Then, the ending state is chosen that has a minimum accumulated error metric. This technique, however, results in higher average BER.
In order to overcome these various problems, a flexible algorithm which can be used to optimize missed detection rate and bit error rate by detecting the correct ending state for each burst of a convolutionally encoded data stream is needed.